We consider the problem of detecting a small subset of defective items from alarge set via non-adaptive "random pooling" group tests. We consider both thecase when the measurements are noiseless, and the case when the measurementsare noisy (the outcome of each group test may be independently faulty withprobability q). Order-optimal results for these scenarios are known in theliterature. We give information-theoretic lower bounds on the query complexityof these problems, and provide corresponding computationally efficientalgorithms that match the lower bounds up to a constant factor. To the best ofour knowledge this work is the first to explicitly estimate such a constantthat characterizes the gap between the upper and lower bounds for theseproblems.
展开▼
